<html>
<head>
  <title>Evernote Export</title>
  <basefont face="微软雅黑" size="2" />
  <meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
  <meta name="exporter-version" content="YXBJ Windows/602326 (zh-CN, DDL); Windows/10.0.0 (Win64); EDAMVersion=V2;"/>
  <style>
    body, td {
      font-family: 微软雅黑;
      font-size: 10pt;
    }
  </style>
</head>
<body>
<a name="1243"/>

<div>
<span><div>通过一系列的有序点生成对应的mesh</div><div><br/></div><div>MeshDrawer.cs 程序入口</div><div><br/></div><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.15);-en-codeblock:true;"><div>using System.Collections;</div><div>using System.Collections.Generic;</div><div>using UnityEngine;</div><div>using LuoHu.Tx3d;</div><div>#if UNITY_EDITOR</div><div>using UnityEditor;</div><div>#endif</div><div>public class MeshDrawer : MonoBehaviour</div><div>{</div><div>    public GameObject sphe;</div><div>    public List&lt;Vector3&gt; index;</div><div>    void Start()</div><div>    {</div><div>    }</div><div>    // Update is called once per frame</div><div>    void Update()</div><div>    {</div><div>        //获取由主摄像机位置到鼠标点击位置的一条射线</div><div>        if (Input.GetMouseButton(0))</div><div>        {</div><div>            if (Camera.main == null)</div><div>                return;</div><div>            Ray ray = Camera.main.ScreenPointToRay(Input.mousePosition);</div><div>            RaycastHit hitInfo;</div><div>            bool isCollider = Physics.Raycast(ray, out hitInfo);</div><div>            //判断射线是否成功发射且是否触发目标物体</div><div>            if (isCollider &amp;&amp; hitInfo.collider.tag == &quot;Road&quot;)</div><div>            {</div><div>                GameObject obj = Instantiate(sphe);</div><div>                obj.transform.position = hitInfo.point;</div><div>                index.Add(hitInfo.point);</div><div>            }</div><div>        }</div><div>        if (Input.GetKeyDown(KeyCode.P))</div><div>        {</div><div>            PloygonEntity obj = new PloygonEntity(index);</div><div>#if UNITY_EDITOR</div><div>            EditorGUIUtility.PingObject(obj.obj);</div><div>#endif</div><div>            index.Clear();</div><div>        }</div><div>    }</div><div>}</div></div><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.15);-en-codeblock:true;"><div>/*</div><div>*******************************************************</div><div>*</div><div>* 文件名称：EarCut</div><div>* 文件描述：三角化相关算法集合</div><div>*</div><div>* 版本：V1.0.0</div><div>*  支持带洞的多边形，需要保证多边形为顺时针，而洞为逆时针顺序</div><div>* *****************************************************</div><div>*/</div><div><br/></div><div><br/></div><div>using System;</div><div>using System.Collections;</div><div>using System.Collections.Generic;</div><div>using UnityEngine;</div><div><br/></div><div><br/></div><div>namespace LuoHu.Tx3d</div><div>{</div><div>    public class EarCut</div><div>    {</div><div>        #region Sub Class</div><div><br/></div><div><br/></div><div>        /// &lt;summary&gt;</div><div>        /// “割耳”点</div><div>        /// &lt;/summary&gt;</div><div>        private class Node : IComparable</div><div>        {</div><div>            #region Members &amp; Properties</div><div><br/></div><div><br/></div><div>            /// &lt;summary&gt;</div><div>            /// vertice index in coordinates array</div><div>            /// &lt;/summary&gt;</div><div>            public int i = -1;</div><div><br/></div><div><br/></div><div>            /// &lt;summary&gt;</div><div>            ///  vertex coordinates</div><div>            /// &lt;/summary&gt;</div><div>            public float x = 0.0f;</div><div>            public float z = 0.0f;</div><div><br/></div><div><br/></div><div>            /// &lt;summary&gt;</div><div>            /// previous and next vertice nodes in a polygon ring</div><div>            /// &lt;/summary&gt;</div><div>            public Node prev = null;</div><div>            public Node next = null;</div><div><br/></div><div><br/></div><div>            /// &lt;summary&gt;</div><div>            /// z-order curve value</div><div>            /// &lt;/summary&gt;</div><div>            public int zOrder = -1;</div><div><br/></div><div><br/></div><div>            /// &lt;summary&gt;</div><div>            /// previous and next nodes in z-order</div><div>            /// &lt;/summary&gt;</div><div>            public Node prevZ = null;</div><div>            public Node nextZ = null;</div><div><br/></div><div><br/></div><div>            /// &lt;summary&gt;</div><div>            /// indicates whether this is a steiner point</div><div>            /// &lt;/summary&gt;</div><div>            public bool steiner = false;</div><div><br/></div><div><br/></div><div>            #endregion</div><div><br/></div><div><br/></div><div>            #region IComparable Implemention</div><div><br/></div><div><br/></div><div>            public int CompareTo(object obj)</div><div>            {</div><div>                try</div><div>                {</div><div>                    Node node = obj as Node;</div><div><br/></div><div><br/></div><div>                    if (this.x &gt; node.x)</div><div>                    {</div><div>                        return 1;</div><div>                    }</div><div>                    else</div><div>                    {</div><div>                        return 0;</div><div>                    }</div><div>                }</div><div>                catch (Exception ex)</div><div>                {</div><div>                    throw new Exception(ex.Message);</div><div>                }</div><div>            }</div><div><br/></div><div><br/></div><div>            #endregion</div><div>        }</div><div><br/></div><div><br/></div><div>        #endregion</div><div><br/></div><div><br/></div><div>        #region Members &amp; Properties</div><div><br/></div><div><br/></div><div>        private static float EPSINON = 0.1f;</div><div><br/></div><div><br/></div><div>        #endregion</div><div><br/></div><div><br/></div><div>        #region Public Methods</div><div><br/></div><div><br/></div><div>        /// &lt;summary&gt;</div><div>        /// “割耳”</div><div>        /// &lt;/summary&gt;</div><div>        public static List&lt;int&gt; CutEar(List&lt;Vector3&gt; data, List&lt;int&gt; holeIndices)</div><div>        {</div><div>            var triangles = new List&lt;int&gt;();</div><div><br/></div><div><br/></div><div>            bool hasHoles = holeIndices != null &amp;&amp; holeIndices.Count &gt; 0;</div><div>            int outerLength = hasHoles ? holeIndices[0] : data.Count;</div><div>            Node outerNode = LinkedList(data, 0, outerLength, true);</div><div><br/></div><div><br/></div><div>            if (outerNode == null)</div><div>            {</div><div>                return triangles;</div><div>            }</div><div><br/></div><div><br/></div><div>            if (hasHoles)</div><div>            {</div><div>                outerNode = EliminateHoles(data, holeIndices, outerNode);</div><div>            }</div><div><br/></div><div><br/></div><div>            float minX = 0.0f;</div><div>            float minZ = 0.0f;</div><div>            float maxX = 0.0f;</div><div>            float maxZ = 0.0f;</div><div>            float size = 0.0f;</div><div><br/></div><div><br/></div><div>            // if the shape is not too simple, we'll use z-order curve hash later; calculate polygon bbox</div><div>            // if (data.Count &gt; 80)</div><div>            if (data.Count &gt; 100)</div><div>            {</div><div>                minX = maxX = data[0].x;</div><div>                minZ = maxZ = data[0].z;</div><div><br/></div><div><br/></div><div>                for (int i = 1; i &lt; outerLength; i++)</div><div>                {</div><div>                    float x = data[i].x;</div><div>                    float z = data[i].z;</div><div>                    if (x &lt; minX) minX = x;</div><div>                    if (z &lt; minZ) minZ = z;</div><div>                    if (x &gt; maxX) maxX = x;</div><div>                    if (z &gt; maxZ) maxZ = z;</div><div>                }</div><div><br/></div><div><br/></div><div>                // minX, minY and size are later used to transform coords into integers for z-order calculation</div><div>                size = Mathf.Max(maxX - minX, maxZ - minZ);</div><div>            }</div><div><br/></div><div><br/></div><div>            EarCutLinked(outerNode, triangles, minX, minZ, size, 0);</div><div><br/></div><div><br/></div><div>            return triangles;</div><div>        }</div><div><br/></div><div><br/></div><div>        #endregion</div><div><br/></div><div><br/></div><div>        #region Private Methods</div><div><br/></div><div><br/></div><div>        /// &lt;summary&gt;</div><div>        /// 使用多边形顶点按照指定顺序创建一个双向循环链表</div><div>        /// &lt;/summary&gt;</div><div>        private static Node LinkedList(List&lt;Vector3&gt; data, int start, int end, bool clockwise)</div><div>        {</div><div>            Node last = null;</div><div><br/></div><div><br/></div><div>            if (clockwise == (SignedArea(data, start, end) &gt;= 0.0))</div><div>            {</div><div>                for (int i = start; i &lt; end; i++)</div><div>                {</div><div>                    last = InsertNode(i, data[i].x, data[i].z, last);</div><div>                }</div><div>            }</div><div>            else</div><div>            {</div><div>                for (int i = end - 1; i &gt;= start; i--)</div><div>                {</div><div>                    last = InsertNode(i, data[i].x, data[i].z, last);</div><div>                }</div><div>            }</div><div><br/></div><div><br/></div><div>            if (last != null &amp;&amp; Equals(last, last.next))</div><div>            {</div><div>                var next = last.next;</div><div>                RemoveNode(last);</div><div>                last = next;</div><div>            }</div><div><br/></div><div><br/></div><div>            return last;</div><div>        }</div><div><br/></div><div><br/></div><div>        /// &lt;summary&gt;</div><div>        /// “割耳”主循环</div><div>        /// &lt;/summary&gt;</div><div>        /// &lt;remarks&gt;</div><div>        /// main ear slicing loop which triangulates a polygon (given as a linked list)</div><div>        /// &lt;/remarks&gt;</div><div>        private static void EarCutLinked(Node ear, List&lt;int&gt; triangles, float minX, float minZ, float size, int pass)</div><div>        {</div><div>            if (ear == null) return;</div><div><br/></div><div><br/></div><div>            // interlink polygon nodes in z-order</div><div>            if (pass == 0 &amp;&amp; size &gt; 0.0f)</div><div>            {</div><div>                IndexCurve(ear, minX, minZ, size);</div><div>            }</div><div><br/></div><div><br/></div><div>            Node stop = ear;</div><div>            Node prev = null;</div><div>            Node next = null;</div><div><br/></div><div><br/></div><div>            // iterate through ears, slicing them one by one</div><div>            while (ear.prev != ear.next)</div><div>            {</div><div>                prev = ear.prev;</div><div>                next = ear.next;</div><div><br/></div><div><br/></div><div>                if (size &gt; 0.0f ? IsEarHashed(ear, minX, minZ, size) : IsEar(ear))</div><div>                {</div><div>                    // cut off the triangle</div><div>                    triangles.Add(prev.i);</div><div>                    triangles.Add(ear.i);</div><div>                    triangles.Add(next.i);</div><div><br/></div><div><br/></div><div>                    RemoveNode(ear);</div><div><br/></div><div><br/></div><div>                    // skipping the next vertice leads to less sliver triangles</div><div>                    ear = next.next;</div><div>                    stop = next.next;</div><div><br/></div><div><br/></div><div>                    continue;</div><div>                }</div><div><br/></div><div><br/></div><div>                ear = next;</div><div><br/></div><div><br/></div><div>                // if we looped through the whole remaining polygon and can't find any more ears</div><div>                if (ear == stop)</div><div>                {</div><div>                    // try filtering points and slicing again</div><div>                    if (pass == 0)</div><div>                    {</div><div>                        EarCutLinked(FilterPoints(ear, null), triangles, minX, minZ, size, 1);</div><div>                    }</div><div>                    else if (pass == 1) // if this didn't work, try curing all small self-intersections locally</div><div>                    {</div><div>                        ear = CureLocalIntersections(ear, triangles);</div><div>                        EarCutLinked(ear, triangles, minX, minZ, size, 2);</div><div>                    }</div><div>                    else if (pass == 2) // as a last resort, try splitting the remaining polygon into two</div><div>                    {</div><div>                        SplitEarCut(ear, triangles, minX, minZ, size);</div><div>                    }</div><div><br/></div><div><br/></div><div>                    return;</div><div>                }</div><div>            }</div><div>        }</div><div><br/></div><div><br/></div><div>        /// &lt;summary&gt;</div><div>        /// 尝试将多边形分割成两个，并分别进行三角化</div><div>        /// &lt;/summary&gt;</div><div>        private static void SplitEarCut(Node start, List&lt;int&gt; triangles, float minX, float minZ, float size)</div><div>        {</div><div>            // look for a valid diagonal that divides the polygon into two</div><div>            var a = start;</div><div><br/></div><div><br/></div><div>            do</div><div>            {</div><div>                var b = a.next.next;</div><div><br/></div><div><br/></div><div>                while (b != a.prev)</div><div>                {</div><div>                    if (a.i != b.i &amp;&amp; IsValidDiagonal(a, b))</div><div>                    {</div><div>                        // split the polygon in two by the diagonal</div><div>                        var c = SplitPolygon(a, b);</div><div><br/></div><div><br/></div><div>                        // filter colinear points around the cuts</div><div>                        a = FilterPoints(a, a.next);</div><div>                        c = FilterPoints(c, c.next);</div><div><br/></div><div><br/></div><div>                        // run earcut on each half</div><div>                        EarCutLinked(a, triangles, minX, minZ, size, 0);</div><div>                        EarCutLinked(c, triangles, minX, minZ, size, 0);</div><div><br/></div><div><br/></div><div>                        return;</div><div>                    }</div><div><br/></div><div><br/></div><div>                    b = b.next;</div><div>                }</div><div><br/></div><div><br/></div><div>                a = a.next;</div><div>            } while (a != start);</div><div>        }</div><div><br/></div><div><br/></div><div>        /// &lt;summary&gt;</div><div>        /// link every hole into the outer loop, producing a single-ring polygon without holes</div><div>        /// &lt;/summary&gt;</div><div>        private static Node EliminateHoles(List&lt;Vector3&gt; data, List&lt;int&gt; holeIndices, Node outerNode)</div><div>        {</div><div>            var queue = new List&lt;Node&gt;();</div><div><br/></div><div><br/></div><div>            for (int i = 0, len = holeIndices.Count; i &lt; len; i++)</div><div>            {</div><div>                var start = holeIndices[i];</div><div>                var end = i &lt; len - 1 ? holeIndices[i + 1] : data.Count;</div><div><br/></div><div><br/></div><div>                var list = LinkedList(data, start, end, false);</div><div><br/></div><div><br/></div><div>                if (list == list.next)</div><div>                {</div><div>                    list.steiner = true;</div><div>                }</div><div><br/></div><div><br/></div><div>                queue.Add(GetLeftmost(list));</div><div>            }</div><div><br/></div><div><br/></div><div>            // Sort</div><div>            queue.Sort();</div><div><br/></div><div><br/></div><div>            // process holes from left to right</div><div>            for (int i = 0; i &lt; queue.Count; i++)</div><div>            {</div><div>                var node = EliminateHole(queue[i], outerNode);</div><div>                if (node != null)</div><div>                {</div><div>                    outerNode = FilterPoints(node, node.next);</div><div>                }</div><div>            }</div><div><br/></div><div><br/></div><div>            return outerNode;</div><div>        }</div><div><br/></div><div><br/></div><div>        /// &lt;summary&gt;</div><div>        /// find a bridge between vertices that connects hole with an outer ring and and link it</div><div>        /// &lt;/summary&gt;</div><div>        private static Node EliminateHole(Node hole, Node outerNode)</div><div>        {</div><div>            outerNode = FindHoleBridge(hole, outerNode);</div><div>            if (outerNode != null)</div><div>            {</div><div>                var b = SplitPolygon(outerNode, hole);</div><div>                return FilterPoints(b, b.next);</div><div>            }</div><div><br/></div><div><br/></div><div>            return null;</div><div>        }</div><div><br/></div><div><br/></div><div>        /// &lt;summary&gt;</div><div>        /// 遍历多边形所有结点，校正局部自相交情形</div><div>        /// &lt;/summary&gt;</div><div>        private static Node CureLocalIntersections(Node start, List&lt;int&gt; triangles)</div><div>        {</div><div>            var p = start;</div><div><br/></div><div><br/></div><div>            do</div><div>            {</div><div>                var a = p.prev;</div><div>                var b = p.next.next;</div><div><br/></div><div><br/></div><div>                if (!Equals(a, b) &amp;&amp;</div><div>                    Intersects(a, p, p.next, b) &amp;&amp;</div><div>                    LocallyInside(a, b) &amp;&amp;</div><div>                    LocallyInside(b, a))</div><div>                {</div><div>                    triangles.Add(a.i);</div><div>                    triangles.Add(p.i);</div><div>                    triangles.Add(b.i);</div><div><br/></div><div><br/></div><div>                    var next = p.next;</div><div><br/></div><div><br/></div><div>                    // remove two nodes involved</div><div>                    RemoveNode(p);</div><div>                    RemoveNode(next);</div><div><br/></div><div><br/></div><div>                    p = start = b;</div><div>                }</div><div><br/></div><div><br/></div><div>                p = p.next;</div><div>            } while (p != start);</div><div><br/></div><div><br/></div><div>            return p;</div><div>        }</div><div><br/></div><div><br/></div><div>        /// &lt;summary&gt;</div><div>        /// 插入一个结点</div><div>        /// &lt;/summary&gt;</div><div>        private static Node InsertNode(int i, float x, float z, Node last)</div><div>        {</div><div>            var p = new Node</div><div>            {</div><div>                i = i,</div><div>                x = x,</div><div>                z = z</div><div>            };</div><div><br/></div><div><br/></div><div>            if (last == null)</div><div>            {</div><div>                p.prev = p;</div><div>                p.next = p;</div><div>            }</div><div>            else</div><div>            {</div><div>                p.next = last.next;</div><div>                p.prev = last;</div><div><br/></div><div><br/></div><div>                last.next.prev = p;</div><div>                last.next = p;</div><div>            }</div><div><br/></div><div><br/></div><div>            return p;</div><div>        }</div><div><br/></div><div><br/></div><div>        /// &lt;summary&gt;</div><div>        /// 移除一个结点</div><div>        /// &lt;/summary&gt;</div><div>        private static void RemoveNode(Node p)</div><div>        {</div><div>            p.next.prev = p.prev;</div><div>            p.prev.next = p.next;</div><div><br/></div><div><br/></div><div>            if (p.prevZ != null)</div><div>            {</div><div>                p.prevZ.nextZ = p.nextZ;</div><div>            }</div><div><br/></div><div><br/></div><div>            if (p.nextZ != null)</div><div>            {</div><div>                p.nextZ.prevZ = p.prevZ;</div><div>            }</div><div>        }</div><div><br/></div><div><br/></div><div>        /// &lt;summary&gt;</div><div>        /// 判断两个结点是否相等</div><div>        /// &lt;/summary&gt;</div><div>        /// &lt;returns&gt;true相等，false不相等&lt;/returns&gt;</div><div>        private static bool Equals(Node p1, Node p2)</div><div>        {</div><div>            if (p1 == null || p2 == null)</div><div>            {</div><div>                Debug.Log(&quot;null&quot;);</div><div>            }</div><div><br/></div><div><br/></div><div>            return p1.x == p2.x &amp;&amp; p1.z == p2.z;</div><div>        }</div><div><br/></div><div><br/></div><div>        /// &lt;summary&gt;</div><div>        /// 判断是否是“耳朵”</div><div>        /// &lt;/summary&gt;</div><div>        /// &lt;param name=&quot;ear&quot;&gt;&lt;/param&gt;</div><div>        /// &lt;returns&gt;&lt;/returns&gt;</div><div>        private static bool IsEar(Node ear)</div><div>        {</div><div>            var a = ear.prev;</div><div>            var b = ear;</div><div>            var c = ear.next;</div><div><br/></div><div><br/></div><div>            if (Area(a, b, c) &gt;= 0.0f)</div><div>            {</div><div>                // reflex, can't be an ear</div><div>                return false;</div><div>            }</div><div><br/></div><div><br/></div><div>            // now make sure we don't have other points inside the potential ear</div><div>            var p = ear.next.next;</div><div>            while (p != ear.prev)</div><div>            {</div><div>                if (PointInTriangle(a, b, c, p) &amp;&amp;</div><div>                    (Area(p.prev, p, p.next) &gt;= 0.0f))</div><div>                {</div><div>                    return false;</div><div>                }</div><div><br/></div><div><br/></div><div>                p = p.next;</div><div>            }</div><div><br/></div><div><br/></div><div>            return true;</div><div>        }</div><div><br/></div><div><br/></div><div>        /// &lt;summary&gt;</div><div>        /// 判断是否是“耳朵”散列？</div><div>        /// &lt;/summary&gt;</div><div>        private static bool IsEarHashed(Node ear, float minX, float minZ, float size)</div><div>        {</div><div>            var a = ear.prev;</div><div>            var b = ear;</div><div>            var c = ear.next;</div><div><br/></div><div><br/></div><div>            if (Area(a, b, c) &gt;= 0.0f)</div><div>            {</div><div>                // reflex, can't be an ear</div><div>                return false;</div><div>            }</div><div><br/></div><div><br/></div><div>            // triangle bbox; min &amp; max are calculated like this for speed</div><div>            var minTX = a.x &lt; b.x ? (a.x &lt; c.x ? a.x : c.x) : (b.x &lt; c.x ? b.x : c.x);</div><div>            var minTZ = a.z &lt; b.z ? (a.z &lt; c.z ? a.z : c.z) : (b.z &lt; c.z ? b.z : c.z);</div><div>            var maxTX = a.x &gt; b.x ? (a.x &gt; c.x ? a.x : c.x) : (b.x &gt; c.x ? b.x : c.x);</div><div>            var maxTZ = a.z &gt; b.z ? (a.z &gt; c.z ? a.z : c.z) : (b.z &gt; c.z ? b.z : c.z);</div><div><br/></div><div><br/></div><div>            // z-order range for the current triangle bbox;</div><div>            int minZOrder = ZOrder(minTX, minTZ, minX, minZ, size);</div><div>            int maxZOrder = ZOrder(maxTX, maxTZ, minX, minZ, size);</div><div><br/></div><div><br/></div><div>            // first look for points inside the triangle in increasing z-order</div><div>            var p = ear.nextZ;</div><div><br/></div><div><br/></div><div>            while (p != null &amp;&amp; p.zOrder &lt;= maxZOrder)</div><div>            {</div><div>                if (p != ear.prev &amp;&amp; p != ear.next &amp;&amp;</div><div>                    PointInTriangle(a, b, c, p) &amp;&amp;</div><div>                    Area(p.prev, p, p.next) &gt;= 0.0f)</div><div>                {</div><div>                    return false;</div><div>                }</div><div><br/></div><div><br/></div><div>                p = p.nextZ;</div><div>            }</div><div><br/></div><div><br/></div><div>            // then look for points in decreasing z-order</div><div>            p = ear.prevZ;</div><div>            while (p != null &amp;&amp; p.zOrder &gt;= minZOrder)</div><div>            {</div><div>                if (p != ear.prev &amp;&amp; p != ear.next &amp;&amp;</div><div>                    PointInTriangle(a, b, c, p) &amp;&amp;</div><div>                    Area(p.prev, p, p.next) &gt;= 0.0f)</div><div>                {</div><div>                    return false;</div><div>                }</div><div><br/></div><div><br/></div><div>                p = p.prevZ;</div><div>            }</div><div><br/></div><div><br/></div><div>            return true;</div><div>        }</div><div><br/></div><div><br/></div><div>        /// &lt;summary&gt;</div><div>        /// 通过对角线分割多边形</div><div>        /// &lt;/summary&gt;</div><div>        /// &lt;remarks&gt;</div><div>        /// link two polygon vertices with a bridge; if the vertices belong to the same ring, it splits polygon into two;</div><div>        /// if one belongs to the outer ring and another to a hole, it merges it into a single ring</div><div>        /// &lt;/remarks&gt;</div><div>        private static Node SplitPolygon(Node a, Node b)</div><div>        {</div><div>            var a2 = new Node</div><div>            {</div><div>                i = a.i,</div><div>                x = a.x,</div><div>                z = a.z</div><div>            };</div><div><br/></div><div><br/></div><div>            var b2 = new Node</div><div>            {</div><div>                i = b.i,</div><div>                x = b.x,</div><div>                z = b.z</div><div>            };</div><div><br/></div><div><br/></div><div>            var an = a.next;</div><div>            var bp = b.prev;</div><div><br/></div><div><br/></div><div>            a.next = b;</div><div>            b.prev = a;</div><div><br/></div><div><br/></div><div>            a2.next = an;</div><div>            an.prev = a2;</div><div><br/></div><div><br/></div><div>            b2.next = a2;</div><div>            a2.prev = b2;</div><div><br/></div><div><br/></div><div>            bp.next = b2;</div><div>            b2.prev = bp;</div><div><br/></div><div><br/></div><div>            return b2;</div><div>        }</div><div><br/></div><div><br/></div><div>        /// &lt;summary&gt;</div><div>        /// 对结点进行排序</div><div>        /// &lt;/summary&gt;</div><div>        /// &lt;remarks&gt;</div><div>        /// Simon Tatham's linked list merge sort algorithm</div><div>        /// &lt;/remarks&gt;</div><div>        private static Node SortLinked(Node list)</div><div>        {</div><div>            int numMerges = 0;</div><div>            int pSize = 0;</div><div>            int qSize = 0;</div><div>            int inSize = 1;</div><div><br/></div><div><br/></div><div>            Node p = null;</div><div>            Node q = null;</div><div>            Node e = null;</div><div>            Node tail = null;</div><div><br/></div><div><br/></div><div>            do</div><div>            {</div><div>                p = list;</div><div>                list = null;</div><div>                tail = null;</div><div>                numMerges = 0;</div><div><br/></div><div><br/></div><div>                while (p != null)</div><div>                {</div><div>                    numMerges++;</div><div><br/></div><div><br/></div><div>                    q = p;</div><div>                    pSize = 0;</div><div><br/></div><div><br/></div><div>                    for (int i = 0; i &lt; inSize; i++)</div><div>                    {</div><div>                        pSize++;</div><div>                        q = q.nextZ;</div><div><br/></div><div><br/></div><div>                        if (q == null)</div><div>                            break;</div><div>                    }</div><div><br/></div><div><br/></div><div>                    qSize = inSize;</div><div><br/></div><div><br/></div><div>                    while (pSize &gt; 0 || (qSize &gt; 0 &amp;&amp; q != null))</div><div>                    {</div><div>                        if (pSize == 0)</div><div>                        {</div><div>                            e = q;</div><div>                            q = q.nextZ;</div><div>                            qSize--;</div><div>                        }</div><div>                        else if (qSize == 0 || q == null)</div><div>                        {</div><div>                            e = p;</div><div>                            p = p.nextZ;</div><div>                            pSize--;</div><div>                        }</div><div>                        else if (p.zOrder &lt;= q.zOrder)</div><div>                        {</div><div>                            e = p;</div><div>                            p = p.nextZ;</div><div>                            pSize--;</div><div>                        }</div><div>                        else</div><div>                        {</div><div>                            e = q;</div><div>                            q = q.nextZ;</div><div>                            qSize--;</div><div>                        }</div><div><br/></div><div><br/></div><div>                        if (tail != null)</div><div>                        {</div><div>                            tail.nextZ = e;</div><div>                        }</div><div>                        else</div><div>                        {</div><div>                            list = e;</div><div>                        }</div><div><br/></div><div><br/></div><div>                        e.prevZ = tail;</div><div>                        tail = e;</div><div>                    }</div><div><br/></div><div><br/></div><div>                    p = q;</div><div>                }</div><div><br/></div><div><br/></div><div>                tail.nextZ = null;</div><div>                inSize *= 2;</div><div>            } while (numMerges &gt; 1);</div><div><br/></div><div><br/></div><div>            return list;</div><div>        }</div><div><br/></div><div><br/></div><div>        /// &lt;summary&gt;</div><div>        /// 相邻多边形节点次序（interlink polygon nodes in z-order）</div><div>        /// &lt;/summary&gt;</div><div>        private static void IndexCurve(Node start, float minX, float minZ, float size)</div><div>        {</div><div>            var p = start;</div><div><br/></div><div><br/></div><div>            do</div><div>            {</div><div>                if (p.zOrder == -1)</div><div>                {</div><div>                    p.zOrder = ZOrder(p.x, p.z, minX, minZ, size);</div><div>                }</div><div><br/></div><div><br/></div><div>                p.prevZ = p.prev;</div><div>                p.nextZ = p.next;</div><div>                p = p.next;</div><div>            } while (p != start);</div><div><br/></div><div><br/></div><div>            p.prevZ.nextZ = null;</div><div>            p.prevZ = null;</div><div><br/></div><div><br/></div><div>            SortLinked(p);</div><div>        }</div><div><br/></div><div><br/></div><div>        /// &lt;summary&gt;</div><div>        /// 判断两条线段是否相交</div><div>        /// &lt;/summary&gt;</div><div>        /// &lt;remarks&gt;</div><div>        /// &lt;/remarks&gt;</div><div>        private static bool Intersects(Node p1, Node q1, Node p2, Node q2)</div><div>        {</div><div>            if ((Equals(p1, q1) &amp;&amp; Equals(p2, q2)) ||</div><div>                (Equals(p1, q2) &amp;&amp; Equals(p2, q1)))</div><div>            {</div><div>                return true;</div><div>            }</div><div><br/></div><div><br/></div><div>            return (Area(p1, q1, p2) &gt; 0.0 != Area(p1, q1, q2) &gt; 0.0) &amp;&amp;</div><div>                (Area(p2, q2, p1) &gt; 0.0 != Area(p2, q2, q1) &gt; 0.0);</div><div>        }</div><div><br/></div><div><br/></div><div>        /// &lt;summary&gt;</div><div>        /// 检测多边形的对角线是否与多边形的边相交</div><div>        /// &lt;/summary&gt;</div><div>        private static bool IntersectsPolygon(Node a, Node b)</div><div>        {</div><div>            var p = a;</div><div><br/></div><div><br/></div><div>            do</div><div>            {</div><div>                if (p.i == a.i &amp;&amp; p.next.i != a.i &amp;&amp;</div><div>                    p.i != b.i &amp;&amp; p.next.i != b.i &amp;&amp;</div><div>                    Intersects(p, p.next, a, b))</div><div>                {</div><div>                    return true;</div><div>                }</div><div><br/></div><div><br/></div><div>                p = p.next;</div><div>            } while (p != a);</div><div><br/></div><div><br/></div><div>            return false;</div><div>        }</div><div><br/></div><div><br/></div><div>        /// &lt;summary&gt;</div><div>        /// 查找多边形最坐标结点</div><div>        /// &lt;/summary&gt;</div><div>        private static Node GetLeftmost(Node start)</div><div>        {</div><div>            var p = start;</div><div>            var leftmost = start;</div><div><br/></div><div><br/></div><div>            do</div><div>            {</div><div>                if (p.x &lt; leftmost.x)</div><div>                {</div><div>                    leftmost = p;</div><div>                }</div><div><br/></div><div><br/></div><div>                p = p.next;</div><div>            } while (p != start);</div><div><br/></div><div><br/></div><div>            return leftmost;</div><div>        }</div><div><br/></div><div><br/></div><div>        /// &lt;summary&gt;</div><div>        /// 查找多边形内部洞与外边的连接点</div><div>        /// &lt;/summary&gt;</div><div>        /// &lt;remarks&gt;David Eberly's algorithm&lt;/remarks&gt;</div><div>        private static Node FindHoleBridge(Node hole, Node outerNode)</div><div>        {</div><div>            var p = outerNode;</div><div><br/></div><div><br/></div><div>            var hx = hole.x;</div><div>            var hz = hole.z;</div><div>            var qx = float.NegativeInfinity;</div><div><br/></div><div><br/></div><div>            Node m = null;</div><div><br/></div><div><br/></div><div>            // find a segment intersected by a ray from the hole's leftmost point to the left;</div><div>            // segment's endpoint with lesser x will be potential connection point</div><div>            do</div><div>            {</div><div>                if ((hz &lt;= p.z &amp;&amp; hz &gt;= p.next.z) ||</div><div>                    (hz &lt;= p.next.z &amp;&amp; hz &gt;= p.z))</div><div>                {</div><div>                    var x = p.x + (hz - p.z) * (p.next.x - p.x) / (p.next.z - p.z);</div><div>                    if (x &lt;= hx &amp;&amp; x &gt; qx)</div><div>                    {</div><div>                        qx = x;</div><div><br/></div><div><br/></div><div>                        if (x == hx)</div><div>                        {</div><div>                            if (hz == p.z)</div><div>                            {</div><div>                                return p;</div><div>                            }</div><div><br/></div><div><br/></div><div>                            if (hz == p.next.z)</div><div>                            {</div><div>                                return p.next;</div><div>                            }</div><div>                        }</div><div><br/></div><div><br/></div><div>                        m = p.x &lt; p.next.x ? p : p.next;</div><div>                    }</div><div>                }</div><div><br/></div><div><br/></div><div>            } while (p != outerNode);</div><div><br/></div><div><br/></div><div>            if (m == null)</div><div>            {</div><div>                return null;</div><div>            }</div><div><br/></div><div><br/></div><div>            // hole touches outer segment; pick lower endpoint</div><div>            if (hx == qx)</div><div>            {</div><div>                return m.prev;</div><div>            }</div><div><br/></div><div><br/></div><div>            // look for points inside the triangle of hole point, segment intersection and endpoint;</div><div>            // if there are no points found, we have a valid connection;</div><div>            // otherwise choose the point of the minimum angle with the ray as connection point</div><div><br/></div><div><br/></div><div>            var stop = m;</div><div><br/></div><div><br/></div><div>            var mx = m.x;</div><div>            var mz = m.z;</div><div>            var tanMin = float.PositiveInfinity;</div><div><br/></div><div><br/></div><div>            p = m.next;</div><div><br/></div><div><br/></div><div>            while (p != stop)</div><div>            {</div><div>                if (hx &gt;= p.x &amp;&amp; p.x &gt;= mx &amp;&amp;</div><div>                    PointInTriangle(hz &lt; mz ? hx : qx, hz, mx, mz, hz &lt; mz ? qx : hx, hz, p.x, p.z))</div><div>                {</div><div>                    var tan = Mathf.Abs(hz - p.z) / (hx - p.x); // tangential</div><div><br/></div><div><br/></div><div>                    if ((tan &lt; tanMin || (tan == tanMin &amp;&amp; p.x &gt; m.x)) &amp;&amp;</div><div>                        LocallyInside(p, hole))</div><div>                    {</div><div>                        m = p;</div><div>                        tanMin = tan;</div><div>                    }</div><div>                }</div><div><br/></div><div><br/></div><div>                p = p.next;</div><div>            }</div><div><br/></div><div><br/></div><div>            return m;</div><div>        }</div><div><br/></div><div><br/></div><div>        /// &lt;summary&gt;</div><div>        /// 检测多边形的对角线是否在多边形内部</div><div>        /// &lt;/summary&gt;</div><div>        private static bool LocallyInside(Node a, Node b)</div><div>        {</div><div>            return Area(a.prev, a, a.next) != 0.0f ?</div><div>                Area(a, b, a.next) &gt;= 0.0f &amp;&amp; Area(a, a.prev, b) &gt;= 0.0f :</div><div>                Area(a, b, a.prev) &gt;= 0.0f &amp;&amp; Area(a, a.next, b) &lt; 0.0f;</div><div>        }</div><div><br/></div><div><br/></div><div>        /// &lt;summary&gt;</div><div>        /// 检测多边形对角线中心点是否在多边形内部</div><div>        /// &lt;/summary&gt;</div><div>        private static bool MiddleInside(Node a, Node b)</div><div>        {</div><div>            var p = a;</div><div>            var inside = false;</div><div>            var px = (a.x + b.x) * 0.5f;</div><div>            var pz = (a.z + b.z) * 0.5f;</div><div><br/></div><div><br/></div><div>            do</div><div>            {</div><div>                if (((p.z &gt; pz) != (p.next.z &gt; pz)) &amp;&amp;</div><div>                    (px &lt; ((p.next.x - px) * (pz - p.z) / (p.next.z - p.z) + p.x)))</div><div>                {</div><div>                    inside = !inside;</div><div>                }</div><div><br/></div><div><br/></div><div>                p = p.next;</div><div>            } while (p != a);</div><div><br/></div><div><br/></div><div>            return inside;</div><div>        }</div><div><br/></div><div><br/></div><div>        /// &lt;summary&gt;</div><div>        /// 判断多边形中的两点是否构成有效对角线</div><div>        /// &lt;/summary&gt;</div><div>        private static bool IsValidDiagonal(Node a, Node b)</div><div>        {</div><div>            return a.next.i != b.i &amp;&amp;</div><div>                a.prev.i != b.i &amp;&amp;</div><div>                !IntersectsPolygon(a, b) &amp;&amp;</div><div>                LocallyInside(a, b) &amp;&amp;</div><div>                LocallyInside(b, a) &amp;&amp;</div><div>                MiddleInside(a, b);</div><div>        }</div><div><br/></div><div><br/></div><div>        /// &lt;summary&gt;</div><div>        /// 过滤掉共线或重复的结点</div><div>        /// &lt;/summary&gt;</div><div>        private static Node FilterPoints(Node start, Node end)</div><div>        {</div><div>            if (start == null) return start;</div><div><br/></div><div><br/></div><div>            if (end == null) end = start;</div><div><br/></div><div><br/></div><div>            var p = start;</div><div>            var again = false;</div><div><br/></div><div><br/></div><div>            do</div><div>            {</div><div>                again = false;</div><div><br/></div><div><br/></div><div>                if (!p.steiner &amp;&amp; (Equals(p, p.next) || Area(p.prev, p, p.next) == 0.0f))</div><div>                {</div><div>                    var prev = p.prev;</div><div>                    RemoveNode(p);</div><div>                    p = end = prev;</div><div>                    if (p == p.next)</div><div>                    {</div><div>                        return null;</div><div>                    }</div><div><br/></div><div><br/></div><div>                    again = true;</div><div>                }</div><div>                else</div><div>                {</div><div>                    p = p.next;</div><div>                }</div><div>            } while (again || p != end);</div><div><br/></div><div><br/></div><div>            return end;</div><div>        }</div><div><br/></div><div><br/></div><div>        /// &lt;summary&gt;</div><div>        /// 计算给定坐标点和外包大小的结点z-order（z-order of a point given coords and size of the data bounding box）</div><div>        /// &lt;/summary&gt;</div><div>        private static int ZOrder(float x, float z, float minX, float minZ, float size)</div><div>        {</div><div>            // coords are transformed into non-negative 15-bit integer range</div><div>            int _x = (int)(32767 * (x - minX) / size);</div><div>            int _z = (int)(32767 * (z - minZ) / size);</div><div><br/></div><div><br/></div><div>            _x = (_x | (_x &lt;&lt; 8)) &amp; 0x00FF00FF;</div><div>            _x = (_x | (_x &lt;&lt; 4)) &amp; 0x0F0F0F0F;</div><div>            _x = (_x | (_x &lt;&lt; 2)) &amp; 0x33333333;</div><div>            _x = (_x | (_x &lt;&lt; 1)) &amp; 0x55555555;</div><div><br/></div><div><br/></div><div>            _z = (_z | (_z &lt;&lt; 8)) &amp; 0x00FF00FF;</div><div>            _z = (_z | (_z &lt;&lt; 4)) &amp; 0x0F0F0F0F;</div><div>            _z = (_z | (_z &lt;&lt; 2)) &amp; 0x33333333;</div><div>            _z = (_z | (_z &lt;&lt; 1)) &amp; 0x55555555;</div><div><br/></div><div><br/></div><div>            return _x | (_z &lt;&lt; 1);</div><div>        }</div><div><br/></div><div><br/></div><div>        /// &lt;summary&gt;</div><div>        /// 判断一个点是否在三角形内</div><div>        /// &lt;/summary&gt;</div><div>        /// &lt;returns&gt;true在，false不在&lt;/returns&gt;</div><div>        private static bool PointInTriangle(Node a, Node b, Node c, Node d)</div><div>        {</div><div>            var SABC = Mathf.Abs(Area(a, b, c)) * 0.5f;</div><div>            var SADB = Mathf.Abs(Area(a, d, b)) * 0.5f;</div><div>            var SBDC = Mathf.Abs(Area(b, d, c)) * 0.5f;</div><div>            var SADC = Mathf.Abs(Area(a, d, c)) * 0.5f;</div><div><br/></div><div><br/></div><div>            var S = SABC - (SADB + SBDC + SADC);</div><div>            if (S &gt; -EPSINON &amp;&amp; S &lt; EPSINON)</div><div>            {</div><div>                return true;</div><div>            }</div><div><br/></div><div><br/></div><div>            return false;</div><div>        }</div><div><br/></div><div><br/></div><div>        /// &lt;summary&gt;</div><div>        /// 判断一个点是否在三角形内</div><div>        /// &lt;/summary&gt;</div><div>        /// &lt;returns&gt;true在，false不在&lt;/returns&gt;</div><div>        private static bool PointInTriangle(float x0, float y0,</div><div>            float x1, float y1,</div><div>            float x2, float y2,</div><div>            float x3, float y3)</div><div>        {</div><div>            var SABC = Mathf.Abs(Area(x0, y0, x1, y1, x2, y2)) * 0.5f;</div><div>            var SADB = Mathf.Abs(Area(x0, y0, x3, y3, x1, y1)) * 0.5f;</div><div>            var SBDC = Mathf.Abs(Area(x1, y1, x3, y3, x2, y2)) * 0.5f;</div><div>            var SADC = Mathf.Abs(Area(x0, y0, x3, y3, x2, y2)) * 0.5f;</div><div><br/></div><div><br/></div><div>            var S = SABC - (SADB + SBDC + SADC);</div><div>            if (S &gt; -EPSINON &amp;&amp; S &lt; EPSINON)</div><div>            {</div><div>                return true;</div><div>            }</div><div><br/></div><div><br/></div><div>            return false;</div><div>        }</div><div><br/></div><div><br/></div><div>        /// &lt;summary&gt;</div><div>        /// 计算三角形有向面积（三角形面积的2倍）</div><div>        /// &lt;/summary&gt;</div><div>        /// &lt;remarks&gt;</div><div>        /// 结果大于0.0，p、q、r按逆时针排列</div><div>        /// 结果等于0.0，p、q、r在一条直线上</div><div>        /// 结果小于0.0，p、q、r按顺时针排列</div><div>        /// &lt;/remarks&gt;</div><div>        /// &lt;returns&gt;三角形有向面积&lt;/returns&gt;</div><div>        private static float Area(Node p, Node q, Node r)</div><div>        {</div><div>            return Area(p.x, p.z, q.x, q.z, r.x, r.z);</div><div>        }</div><div><br/></div><div><br/></div><div>        /// &lt;summary&gt;</div><div>        /// 计算三角形有向面积（三角形面积2倍）</div><div>        /// &lt;/summary&gt;</div><div>        /// &lt;returns&gt;三角形有向面积&lt;/returns&gt;</div><div>        private static float Area(float x0, float y0,</div><div>            float x1, float y1,</div><div>            float x2, float y2)</div><div>        {</div><div>            return x0 * y1 + x2 * y0 + x1 * y2 - x2 * y1 - x0 * y2 - x1 * y0;</div><div>        }</div><div><br/></div><div><br/></div><div>        /// &lt;summary&gt;</div><div>        /// 计算多边形有向面积（多边形面积的2倍）</div><div>        /// &lt;/summary&gt;</div><div>        /// &lt;param name=&quot;data&quot;&gt;顶点数据&lt;/param&gt;</div><div>        /// &lt;param name=&quot;start&quot;&gt;起始顶点索引&lt;/param&gt;</div><div>        /// &lt;param name=&quot;end&quot;&gt;结束顶点索引&lt;/param&gt;</div><div>        /// &lt;remarks&gt;</div><div>        /// 结果大于等于0.0，多边形顶点按顺时针排序</div><div>        /// 结果小于0.0，多边形顶点按逆时针排序</div><div>        /// &lt;/remarks&gt;</div><div>        /// &lt;returns&gt;多边形有向面积&lt;/returns&gt;</div><div>        private static float SignedArea(List&lt;Vector3&gt; data, int start, int end)</div><div>        {</div><div>            var sum = 0.0f;</div><div><br/></div><div><br/></div><div>            for (int i = start; i &lt; end; i++)</div><div>            {</div><div>                var next = (i + 1) == end ? start : i + 1;</div><div>                var dx = data[next].x - data[i].x;</div><div>                var dz = data[next].z + data[i].z;</div><div>                sum += (dx * dz);</div><div>            }</div><div><br/></div><div><br/></div><div>            return sum;</div><div>        }</div><div><br/></div><div><br/></div><div>        #endregion</div><div>    }</div><div>}</div></div><div><br/></div><div>创建实体</div><div>PloygonEntity.cs</div><div><br/></div><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.15);-en-codeblock:true;"><div>using System.Collections.Generic;</div><div>using UnityEngine;</div><div>namespace LuoHu.Tx3d</div><div>{</div><div>    /// &lt;summary&gt;</div><div>    /// 矢量面实体</div><div>    /// &lt;/summary&gt;</div><div>    public class PloygonEntity</div><div>    {</div><div>        #region 字段</div><div>        /// &lt;summary&gt;</div><div>        /// 点集</div><div>        /// &lt;/summary&gt;</div><div>        private List&lt;Vector3&gt; points = new List&lt;Vector3&gt;();</div><div>        /// &lt;summary&gt;</div><div>        /// 顶点集合</div><div>        /// &lt;/summary&gt;</div><div>        private List&lt;Vector3&gt; vertexs = new List&lt;Vector3&gt;();</div><div>        /// &lt;summary&gt;</div><div>        /// 索引集合</div><div>        /// &lt;/summary&gt;</div><div>        private List&lt;int&gt; triangles = new List&lt;int&gt;();</div><div>        /// &lt;summary&gt;</div><div>        /// 实体</div><div>        /// &lt;/summary&gt;</div><div>        public GameObject obj;</div><div>        private MeshFilter meshFilter;</div><div>        private MeshRenderer meshRenderer;</div><div>        private Material material;</div><div>        #endregion</div><div>        #region Methods</div><div>        #region Public</div><div>        /// &lt;summary&gt;</div><div>        /// 创建矢量面实体</div><div>        /// &lt;/summary&gt;</div><div>        /// &lt;param name=&quot;points&quot;&gt;&lt;/param&gt;</div><div>        public PloygonEntity(List&lt;Vector3&gt; points)</div><div>        {</div><div>            this.points = points;</div><div>            SetVertexTrianglesData();</div><div>            RenderPloygon();</div><div>        }</div><div>        public void AddPoint(Vector3 point)</div><div>        {</div><div>            point.y = 0;</div><div>            points.Add(point);</div><div>            SetVertexTrianglesData();</div><div>            RenderPloygon();</div><div>        }</div><div>        public void ChangePoint(Vector3 vector3)</div><div>        {</div><div>            if (points.Count &gt; 0)</div><div>            {</div><div>                vector3.y = 0;</div><div>                points[points.Count - 1] = vector3;</div><div>                SetVertexTrianglesData();</div><div>                RenderPloygon();</div><div>            }</div><div>        }</div><div>        #endregion</div><div>        #region Private</div><div>        /// &lt;summary&gt;</div><div>        /// 设置顶点三角形数据</div><div>        /// &lt;/summary&gt;</div><div>        private void SetVertexTrianglesData()</div><div>        {</div><div>            for (int i = 0; i &lt; points.Count; i++)</div><div>            {</div><div>                Debug.Log(points[i]);</div><div>            }</div><div>            PolygonData data = GetPolygonData(points);</div><div>            vertexs = data.Vertices;</div><div>            triangles = data.Indices;</div><div>        }</div><div>        /// &lt;summary&gt;</div><div>        /// 渲染面</div><div>        /// &lt;/summary&gt;</div><div>        private void RenderPloygon()</div><div>        {</div><div>            if (obj == null)</div><div>                obj = new GameObject();</div><div>            if (meshFilter == null)</div><div>                meshFilter = obj.AddComponent&lt;MeshFilter&gt;();</div><div>            meshFilter.mesh = new Mesh</div><div>            {</div><div>                vertices = vertexs.ToArray(),</div><div>                triangles = triangles.ToArray(),</div><div>            };</div><div>            meshFilter.mesh.RecalculateNormals();</div><div>            if (meshRenderer == null)</div><div>                meshRenderer = obj.AddComponent&lt;MeshRenderer&gt;();</div><div>            SetMatraial();</div><div>            meshRenderer.material = material;</div><div>            if (points.Count &gt; 2)</div><div>            {</div><div>                UpdateLineGameObject();</div><div>            }</div><div>        }</div><div>        /// &lt;summary&gt;</div><div>        /// 设置材质</div><div>        /// &lt;/summary&gt;</div><div>        private void SetMatraial()</div><div>        {</div><div>            //if (material == null)</div><div>            //{</div><div>            //    material = new Material(Resources.Load&lt;Shader&gt;(&quot;shader/Ploygon&quot;));</div><div>            //}</div><div>            //material.SetColor(&quot;_PloygonColor&quot;, Color.yellow);</div><div>            //material.SetFloat(&quot;_Scale&quot;, 1.2f);</div><div>            //material.SetVector(&quot;_CenterPointPosition&quot;, GetCenterPointPos());</div><div>            if (material == null)</div><div>            {</div><div>                material =  Resources.Load&lt;Material&gt;(&quot;shader/Ploygon&quot;);</div><div>            }</div><div>        }</div><div>        // &lt;summary&gt;</div><div>        /// 根据顶点集合获取矢量面数据</div><div>        /// &lt;/summary&gt;</div><div>        private PolygonData GetPolygonData(List&lt;Vector3&gt; points)</div><div>        {</div><div>            return TriangulateUtil.GeneratePolygon(points);</div><div>        }</div><div>        private Vector3 GetCenterPointPos()</div><div>        {</div><div>            Vector3 point = Vector3.zero;</div><div>            for (int i = 0; i &lt; points.Count; i++)</div><div>            {</div><div>                point += Camera.main.WorldToScreenPoint(points[i]);</div><div>            }</div><div>            point /= points.Count;</div><div>            return point;</div><div>        }</div><div>        /// &lt;summary&gt;</div><div>        /// 创建边框线Mesh</div><div>        /// &lt;/summary&gt;</div><div>        /// &lt;param name=&quot;start&quot;&gt;线起点&lt;/param&gt;</div><div>        /// &lt;param name=&quot;end&quot;&gt;线终点&lt;/param&gt;</div><div>        /// &lt;returns&gt;Mesh对象&lt;/returns&gt;</div><div>        private Mesh CreateLineMesh()</div><div>        {</div><div>            List&lt;Vector3&gt; vertex = new List&lt;Vector3&gt;();</div><div>            var indices = new List&lt;int&gt;();</div><div>            for (int i = 0; i &lt; points.Count; i++)</div><div>            {</div><div>                vertex.Add(points[i]);</div><div>                indices.Add(i);</div><div>                if (i &gt; 0 &amp;&amp; i &lt; points.Count - 1)</div><div>                {</div><div>                    indices.Add(i);</div><div>                }</div><div>            }</div><div>            for (int i = points.Count - 1; i &gt;= 0; i--)</div><div>            {</div><div>                indices.Add(i);</div><div>                if (i &gt; 0 &amp;&amp; i &lt; points.Count - 1)</div><div>                {</div><div>                    indices.Add(i);</div><div>                }</div><div>            }</div><div>            Mesh mesh = new Mesh();</div><div>            mesh.SetVertices(points);</div><div>            mesh.SetIndices(indices.ToArray(), MeshTopology.Lines, 0);</div><div>            return mesh;</div><div>        }</div><div>        MeshFilter goMeshFilter;</div><div>        MeshRenderer goMeshRenderer;</div><div>        GameObject go;</div><div>        private void UpdateLineGameObject()</div><div>        {</div><div>            if (go == null)</div><div>            {</div><div>                go = new GameObject(&quot;line&quot;);</div><div>            }</div><div>            if (goMeshFilter == null)</div><div>            {</div><div>                goMeshFilter = go.AddComponent&lt;MeshFilter&gt;();</div><div>            }</div><div>            goMeshFilter.mesh = CreateLineMesh();</div><div>            if (goMeshRenderer == null)</div><div>            {</div><div>                goMeshRenderer = go.AddComponent&lt;MeshRenderer&gt;();</div><div>            }</div><div>            goMeshRenderer.material.color = Color.red;</div><div>        }</div><div>        #endregion</div><div>        #endregion</div><div>    }</div><div>}</div></div><div>扩展算法</div><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.15);-en-codeblock:true;"><div>/*</div><div>*******************************************************</div><div>*</div><div>* 文件名称：TriangulateUtil</div><div>* 文件描述：三角化相关算法集合</div><div>* *****************************************************</div><div>*/</div><div>using System;</div><div>using System.Collections;</div><div>using System.Collections.Generic;</div><div>using UnityEngine;</div><div>namespace LuoHu.Tx3d</div><div>{</div><div>    /// &lt;summary&gt;</div><div>    /// 三角化相关算法集合</div><div>    /// &lt;/summary&gt;</div><div>    public class TriangulateUtil</div><div>    {</div><div>        #region Public Methods       </div><div>        /// &lt;summary&gt;</div><div>        /// 多边形三角化</div><div>        /// &lt;/summary&gt;</div><div>        /// &lt;param name=&quot;polygon&quot;&gt;&lt;/param&gt;</div><div>        /// &lt;returns&gt;返回顺时针方向的三角形数据&lt;/returns&gt;</div><div>        public static PolygonData GeneratePolygon(List&lt;Vector3&gt; polygon)</div><div>        {</div><div>            PolygonData polygonData = new PolygonData();</div><div>            //保证是顺时针队列</div><div>            if (!IsClockwise(polygon))</div><div>            {</div><div>                //排序</div><div>                polygonData.Vertices.AddRange(Reverse(polygon));</div><div>            }</div><div>            else</div><div>                polygonData.Vertices.AddRange(polygon);</div><div>            //不带洞的多边形</div><div>            polygonData.Indices = EarCut.CutEar(polygonData.Vertices, new  List&lt;int&gt;());</div><div>            return polygonData;</div><div>        }</div><div>        /// &lt;summary&gt;</div><div>        /// 带洞多边形三角化</div><div>        /// &lt;/summary&gt;</div><div>        /// &lt;param name=&quot;polygon&quot;&gt;多边形&lt;/param&gt;</div><div>        /// &lt;param name=&quot;indices&quot;&gt;孔洞数组&lt;/param&gt;</div><div>        /// &lt;returns&gt;返回顺时针方向的三角形数据&lt;/returns&gt;</div><div>        public static PolygonData GeneratePolygon(List&lt;Vector3&gt; polygon,  List&lt;Vector3&gt;[] holes)</div><div>        {</div><div>            PolygonData polygonData = new PolygonData();</div><div>            //保证是顺时针队列</div><div>            if (!IsClockwise(polygon))</div><div>            {</div><div>                //排序</div><div>                polygonData.Vertices.AddRange(Reverse(polygon));</div><div>            }</div><div>            else</div><div>                polygonData.Vertices.AddRange(polygon);</div><div>            var holeIndices = new List&lt;int&gt;();</div><div>            int offset = polygon.Count;</div><div>            //孔洞需要逆时针</div><div>            foreach (var hole in holes)</div><div>            {</div><div>                if (IsClockwise(hole))</div><div>                {</div><div>                    //排序</div><div>                    polygonData.Vertices.AddRange(Reverse(hole));</div><div>                }</div><div>                else</div><div>                    polygonData.Vertices.AddRange(hole);</div><div>                holeIndices.Add(offset);</div><div>                offset += hole.Count;</div><div>            }</div><div>            //带洞的多边形</div><div>            polygonData.Indices = EarCut.CutEar(polygonData.Vertices, holeIndices);</div><div>            return polygonData;</div><div>        }</div><div>        /// &lt;summary&gt;</div><div>        /// 判断坐标序列是否是顺时针排列</div><div>        /// &lt;/summary&gt;</div><div>        /// &lt;param name=&quot;ring&quot;&gt;坐标序列&lt;/param&gt;</div><div>        /// &lt;returns&gt;true顺时针，false逆时针&lt;/returns&gt;</div><div>        public static bool IsClockwise(List&lt;Vector3&gt; ring)</div><div>        {</div><div>            var val = 0.0;</div><div>            for (int i = 0, il = ring.Count; i &lt; il; i++)</div><div>            {</div><div>                var next = (i + 1) % il;</div><div>                var point = ring[i];</div><div>                var nextPoint = ring[next];</div><div>                val += (nextPoint.x - point.x) * (nextPoint.z + point.z);</div><div>            }</div><div>            return val &gt; 0.0;</div><div>        }</div><div>        /// &lt;summary&gt;</div><div>        /// 计算三角面法向量</div><div>        /// &lt;/summary&gt;</div><div>        /// &lt;param name=&quot;a&quot;&gt;顶点a&lt;/param&gt;</div><div>        /// &lt;param name=&quot;b&quot;&gt;顶点b&lt;/param&gt;</div><div>        /// &lt;param name=&quot;c&quot;&gt;顶点c&lt;/param&gt;</div><div>        /// &lt;returns&gt;单位化的法向量&lt;/returns&gt;</div><div>        public static Vector3 CalculateFaceNormal(Vector3 a, Vector3 b, Vector3 c)</div><div>        {</div><div>            var side1 = b - a;</div><div>            var side2 = c - a;</div><div>            var n = Vector3.Cross(side1, side2);</div><div>            return n.normalized;</div><div>        }</div><div>        /// &lt;summary&gt;</div><div>        /// 射线和三角面相交检测</div><div>        /// &lt;/summary&gt;</div><div>        /// &lt;param name=&quot;ray&quot;&gt;&lt;/param&gt;</div><div>        /// &lt;param name=&quot;a&quot;&gt;&lt;/param&gt;</div><div>        /// &lt;param name=&quot;b&quot;&gt;&lt;/param&gt;</div><div>        /// &lt;param name=&quot;c&quot;&gt;&lt;/param&gt;</div><div>        /// &lt;param name=&quot;distance&quot;&gt;&lt;/param&gt;</div><div>        /// &lt;param name=&quot;positiveSide&quot;&gt;是否检测正面&lt;/param&gt;</div><div>        /// &lt;param name=&quot;negativeSide&quot;&gt;是否检测反面&lt;/param&gt;</div><div>        /// &lt;returns&gt;&lt;/returns&gt;</div><div>        public static bool Raycast(Ray ray, Vector3 a, Vector3 b, Vector3 c, out  float distance, bool positiveSide = true, bool negativeSide = true)</div><div>        {</div><div>            distance = 0;</div><div>            Vector3 normal = CalculateFaceNormal(a, b, c);</div><div>            float t;</div><div>            {</div><div>                float denom = Vector3.Dot(normal, ray.direction);</div><div>                // Check intersect side</div><div>                if (denom &gt; +float.Epsilon)</div><div>                {</div><div>                    if (!negativeSide)</div><div>                        return false;</div><div>                }</div><div>                else if (denom &lt; -float.Epsilon)</div><div>                {</div><div>                    if (!positiveSide)</div><div>                        return false;</div><div>                }</div><div>                else</div><div>                {</div><div>                    // Parallel or triangle area is close to zero when</div><div>                    // the plane normal not normalised.</div><div>                    return false;</div><div>                }</div><div>                t = Vector3.Dot(normal, a - ray.origin) / denom;</div><div>                if (t &lt; 0)</div><div>                {</div><div>                    // Intersection is behind origin</div><div>                    return false;</div><div>                }</div><div>            }</div><div>            //</div><div>            // Calculate the largest area projection plane in X, Y or Z.</div><div>            //</div><div>            int i0, i1;</div><div>            {</div><div>                float n0 = Mathf.Abs(normal[0]);</div><div>                float n1 = Mathf.Abs(normal[1]);</div><div>                float n2 = Mathf.Abs(normal[2]);</div><div>                i0 = 1; i1 = 2;</div><div>                if (n1 &gt; n2)</div><div>                {</div><div>                    if (n1 &gt; n0) i0 = 0;</div><div>                }</div><div>                else</div><div>                {</div><div>                    if (n2 &gt; n0) i1 = 0;</div><div>                }</div><div>            }</div><div>            //</div><div>            // Check the intersection point is inside the triangle.</div><div>            //</div><div>            {</div><div>                float u1 = b[i0] - a[i0];</div><div>                float v1 = b[i1] - a[i1];</div><div>                float u2 = c[i0] - a[i0];</div><div>                float v2 = c[i1] - a[i1];</div><div>                float u0 = t * ray.direction[i0] + ray.origin[i0] - a[i0];</div><div>                float v0 = t * ray.direction[i1] + ray.origin[i1] - a[i1];</div><div>                float alpha = u0 * v2 - u2 * v0;</div><div>                float beta = u1 * v0 - u0 * v1;</div><div>                float area = u1 * v2 - u2 * v1;</div><div>                // epsilon to avoid float precision error</div><div>                const float EPSILON = 1e-6f;</div><div>                float tolerance = -EPSILON * area;</div><div>                if (area &gt; 0)</div><div>                {</div><div>                    if (alpha &lt; tolerance || beta &lt; tolerance || alpha + beta &gt; area  - tolerance)</div><div>                        return false;</div><div>                }</div><div>                else</div><div>                {</div><div>                    if (alpha &gt; tolerance || beta &gt; tolerance || alpha + beta &lt; area  - tolerance)</div><div>                        return false;</div><div>                }</div><div>            }</div><div>            distance = t;</div><div>            return true;</div><div>        }</div><div>        /// &lt;summary&gt;</div><div>        /// 反转坐标序列</div><div>        /// &lt;/summary&gt;</div><div>        /// &lt;param name=&quot;coords&quot;&gt;&lt;/param&gt;</div><div>        /// &lt;returns&gt;&lt;/returns&gt;</div><div>        private static List&lt;Vector3&gt; Reverse(List&lt;Vector3&gt; coords)</div><div>        {</div><div>            List&lt;Vector3&gt; result = new List&lt;Vector3&gt;();</div><div>            for (int i = coords.Count - 1; i &gt;= 0; i--)</div><div>            {</div><div>                result.Add(coords[i]);</div><div>            }</div><div>            return result;</div><div>        }</div><div>        #endregion</div><div>    }</div><div>    /// &lt;summary&gt;</div><div>    /// 多边形数据</div><div>    /// &lt;/summary&gt;</div><div>    public class PolygonData</div><div>    {</div><div>        /// &lt;summary&gt;</div><div>        /// 顶点数据</div><div>        /// &lt;/summary&gt;</div><div>        public List&lt;Vector3&gt; Vertices = new List&lt;Vector3&gt;();</div><div>        /// &lt;summary&gt;</div><div>        /// 索引数据</div><div>        /// &lt;/summary&gt;</div><div>        public List&lt;int&gt; Indices = new List&lt;int&gt;();</div><div>    }</div><div>}</div></div><div><br/></div></span>
</div></body></html> 